package oct2013.linkednode;

public class ValidateBinarySearchTree {
	public boolean isValidBST(TreeNode root) {
		isBst = true;
		dfs(root);
		return isBst;
	}

	boolean isBst;

	int[] dfs(TreeNode root) {
		if (root == null)
			return new int[] { Integer.MAX_VALUE, Integer.MIN_VALUE };
		int[] v = dfs(root.left);
		if (v[1] >= root.val)
			isBst = false;
		int[] u = dfs(root.right);
		if (u[0] <= root.val)
			isBst = false;
		return new int[] { Math.min(v[0], root.val), Math.max(u[1], root.val) };
	}

}